#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
//实现单链表

//单链表的打印
void SLPrint(SLNode* phead)
{
	//assert(phead);
	SLNode* pcur = phead;

	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

//创建一个新的节点
SLNode* SLBuyNode(SLNodeDataType x)
{
	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
	if (newNode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newNode->data = x;//将数据放入新节点的数据中
	newNode->next = NULL;//将新节点的next置为空

	return newNode;
}

//尾插
void SLpushback(SLNode** pphead,SLNodeDataType x)
{
	assert(pphead);
	//两种情况
	//空链表和非空链表
	SLNode* newNode = SLBuyNode(x);

	//空链表
	if (*pphead == NULL)
	{
		*pphead = newNode;
	}
	//非空链表
	else
	{
		SLNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		//跳出循环时，说明ptail现在指向尾节点
		ptail->next = newNode;
	}
}

//头插
void SLpushfront(SLNode** pphead, SLNodeDataType x)
{
	assert(pphead);
	SLNode* newNode = SLBuyNode(x);
	newNode->next = *pphead;
	*pphead = newNode;
}

//尾删
void SLpopback(SLNode** pphead)
{
	//链表不能为空
	assert(pphead && *pphead);

	//链表只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//链表有多个节点
	else
	{
		SLNode* ptail = *pphead;//寻找最后一个节点
		SLNode* prev = *pphead;//寻找倒数第二个节点
		while (ptail->next != NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		//走到这，ptail就是最后一个节点
		//将最后一个结点的空间free掉
		free(ptail);
		ptail = NULL;
		//将倒数第二个节点的next指针置为空
		prev->next = NULL;
	}
}

//头删
void SLpopfront(SLNode** pphead)
{
	assert(pphead && *pphead);
	//记录第二个节点
	SLNode* next = (*pphead)->next;
	//将头节点释放掉
	free(*pphead);
	//赋值
	*pphead = next;
}

//查找
SLNode* SLTFind(SLNode* phead, SLNodeDataType x)
{
	assert(phead);
	while (phead)
	{
		if (phead->data == x)
		{
			return phead;
		}
		phead = phead->next;
	}
	//走到这里说明找不到x
	return NULL;
}

//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLNodeDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	
	SLNode* newnode = SLBuyNode(x);
	SLNode* prev = *pphead;
	//*pphead与pos是否指向同一节点
	if (*pphead == pos)
	{
		//*pphead与pos指向的是同一个节点
		//下面两行代码相当于头插，所以我们可以直接调用头插来实现
		//newnode->next = pos;
		//*pphead = newnode;
		SLpushfront(pphead, x);
	}
	else
	{
		//*pphead与pos指向的不是同一个节点
		//首先找到pos前面的一个节点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//到这里prev就是pos的前一个结点
		//prev newnode pos
		newnode->next = pos;
		prev->next = newnode;
	}
}

//在指定位置之后插入数据
void SLTnsertAfter(SLNode* pos, SLNodeDataType x)
{
	assert(pos);

	//SLNode* next = pos->next;
	SLNode* newnode = SLBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SLpopfront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;//记录pos前一个节点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//走到这prev就已经指向了pos的前一个节点
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

//删除pos节点的后一个节点
void SLEraseAfter(SLNode* pos)
{
	assert(pos && pos->next);

	//if (pos->next == NULL)
	//{
	//	return;
	//}
	SLNode* del = pos->next;//将要删除的节点记录下来
	SLNode* next = pos->next->next;
	free(del);
	del = NULL;
	pos->next = next;
}

//销毁链表
void SListDesTroy(SLNode** pphead)
{
	assert(pphead && *pphead);

	while (*pphead)
	{
		SLNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}